package com.xie.leetcode.array;

//1218. 最长定差子序列
//        给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
//
//        子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
//
//
//
//        示例 1：
//
//        输入：arr = [1,2,3,4], difference = 1
//        输出：4
//        解释：最长的等差子序列是 [1,2,3,4]。
//        示例 2：
//
//        输入：arr = [1,3,5,7], difference = 1
//        输出：1
//        解释：最长的等差子序列是任意单个元素。
//        示例 3：
//
//        输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
//        输出：4
//        解释：最长的等差子序列是 [7,5,3,1]。
//
//
//        提示：
//
//        1 <= arr.length <= 105
//        -104 <= arr[i], difference <= 104

import java.util.HashMap;
import java.util.Map;

/**
 * @author xiezhendong
 * @date 2021/11/5
 */
public class LongestSubsequence {

    public static void main(String[] args) {
        LongestSubsequence longestSubsequence = new LongestSubsequence();
        System.out.println(longestSubsequence.longestSubsequence(new int[]{1, 2, 3, 4}, 1));
        System.out.println(longestSubsequence.longestSubsequence(new int[]{1, 3, 5, 7}, 1));
        System.out.println(longestSubsequence.longestSubsequence(new int[]{1, 5, 7, 8, 5, 3, 4, 2, 1}, -2));
        System.out.println(longestSubsequence.longestSubsequence(new int[]{4, 12, 10, 0, -2, 7, -8, 9, -9, -12, -12, 8, 8}, 0));
    }

    public int longestSubsequence(int[] arr, int difference) {
        int numMax = 0;

        Map<Integer, Integer> valueMap = new HashMap();
        for (int value : arr) {
            Integer val = valueMap.get(value - difference);
            if (val != null) {
                valueMap.put(value, val + 1);
                numMax = Math.max(numMax, val + 1);
            } else {
                valueMap.put(value, 1);
            }
        }

        if (numMax == 0) {
            numMax = 1;
        }

        return numMax;
    }
}
